The prior art discloses the practice of correcting arbitrary 1-bit errors in binary sequences of a particular length n, for example by means of Hamming codes. This is described in Lin, S. and Costello, D. “Error Control Logic”, Prentice Hall, 1983, pp. 79-81, for example.
If, besides the correction of 1-bit errors, 2-bit errors are also recognized, it is possible to use what are known as Hsiao codes, see Lin, S. and Costello, D. “Error Control Coding”, Prentice Hall, 1983, pp. 499-502, for example.
For Hamming codes, the number m of check bits is approximately equal to m≈log2(k), when k is the number of data bits, so that n=k+m. The error correction is known to take place such that first of all a m-component error syndrome is determined from the possibly disrupted data bits and check bits. The m-dimensional error syndrome is then assigned the bit to be corrected that corresponds to the error syndrome by a decoder.
In the case of Hsiao codes, the error correction is likewise effected by the determination of an error syndrome and by a decoder. The number of check bits is one bit greater than for Hamming codes. If the syndrome has an uneven number of ones, a 1-bit error is corrected; if the syndrome has an even number of ones, a 2-bit error is recognized.
The error correction by means of Hamming codes and Hsiao codes is too slow for special applications.
Faster correction, for example of 1-bit errors, is permitted by cross parity codes (for example see: Pflanz, M., Walther, K., Galke, C. and Vierhaus, H., “On-line Error Detection and Correction in Storage Elements with Cross-Parity Check”, Proc. 8-th IOLTW, 2002, pp. 69-73 and Rubinoff, M., “N-dimensional Codes for Detecting and Correcting Multiple Errors”, Comm of the ACM, 1961, pp. 545-551). In the case of these codes, the k data bits are arranged in a rectangular or square array, sometimes also a multidimensional array. On account of the relatively simple description, we assume here that the data are notionally arranged in a rectangular or square two-dimensional array comprising rows and columns. Each data bit is then located precisely in one row and precisely in one column. By way of example, the check bits used can then be the row and column parities. If k is a square number, such as 64=82, then √{square root over (k)}=m′ row parities and √{square root over (k)}=m′ column parities can be used, so that in this case m=2·m′=2·√{square root over (k)} check bits are required.
If the total parity is furthermore used as an additional check bit, m=2·√{square root over (k)}+1 check bits are obtained. For 64 data bits, 17 check bits are then required.
In comparison with the number of 7 checks bits that is required for a Hamming code with 64 data bits, this number is large. To some extent, the error correction is much faster for cross parity codes than for Hamming codes, however.
1-Bit errors in memories or on buses are thus corrected by 1-bit-error-correcting codes. According to the prior art, this is thus usually effected by a Hamming code, if only the correction of 1-bit errors is required, or by a Hsiao code, if, besides the 1-bit error correction, 2-bit error detection is also necessary. If k is the number of data bits, approximately log(k) check bits are required for these codes. For Hamming and Hsiao codes, the number of check bits is an optimum.
The decoding that is effected by means of syndrome determination and decoder takes too long a time in various applications, on account of the circuit depth prescribed by the code.
Alternatively, the correction of 1-bit errors and the detection of 2-bit errors can, as already discussed, be performed by cross parity codes. In this case, the data bits are notionally arranged as a (usually) square array, and the check bits are the row parities and the column parities (and possibly also diagonal parities) of the array.
In this case, the number of check bits is approximately 2 √{square root over (k)}, which is much greater than log(k), particularly when k is relatively large. Thus, 17 check bits are required for a cross parity code with 64 data bits (with total parity included), while a Hsiao code requires only 8 check bits.
However, error correction by means of cross parity codes is much faster than by means of Hamming codes or Hsiao codes.
The error correction is particularly time-critical, since the data can be processed further only after they have been corrected.
In order to be able to observe the requisite clock times, some circuits have involved the use of cross parity codes at particular time-critical points, for example, which replace the initially provided Hsiao codes.
If the requisite time for correcting an error by means of a Hamming code is even just slightly too long to be able to be executed in the current clock cycle, it is possible for a cross parity code to be used instead of a Hamming code, said cross parity code being able to execute the requisite error correction in the current clock cycle.
However, a drawback in this case is that the number of check bits increases abruptly, even though there may be a need for just slight shortening of the time for the error correction. Thus, in the case of 64 data bits, for example, it is necessary to use 17 check bits for a cross parity code instead of the 7 check bits for a Hamming code, even though there may be a need for just a little shortening of the time for the error correction.
To date, there is only the option of choosing between Hamming or Hsiao codes and cross parity codes.
Thus, if the requisite clock time means that it is necessary to decide on a cross parity code, the number of check bits and hence the hardware complexity rise abruptly. This is the case even if an Hsiao code requires a time involvement for decoding that is only just above the necessary clock time.
It would be desirable to determine codes that can be adjusted to suit the requisite clock time for the decoding and at the same time have as small a number of check bits as possible.